package Leetcode.树;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: kirito
 * @Date: 2024/4/2 16:25
 * @Description:
 *所有可能的真二叉树
 * 给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。
 *
 * 答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。
 *
 * 真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：n = 7
 * 输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
 * 示例 2：
 *
 * 输入：n = 3
 * 输出：[[0,0,0]]
 *
 *
 * 提示：
 *
 * 1 <= n <= 20
 */

public class allPossibleFBT {
    /**
     *由于真二叉树中的每个节点恰好有0或2个子节点，如果往一棵真二叉树上添加节点，最少要(在一个叶子下面)添加 2个节点。
     * 这意味着，整棵树以及每棵子树的节点个数一定是奇数 1,3,5,…
     *
     * 对于示例 1，n=7，有4个叶子。枚举根节点的左子树有多少个叶子:
     * 。左子树有 1个叶子，那么右子树有 3 个叶子
     * 左子树有 2个叶子，那么右子树有 2个叶子
     * ·左子树有 3个叶子，那么右子树有1个叶子。
     * 对于每棵子树，我们同样需要生成所有真二叉树，这是一个和原问题相似的，规模更小的子问题
     *
     *
     * @param n
     * @return
     */
    public List<TreeNode> allPossibleFBT(int n) {
        // 如果节点的数量是偶数，则没有可能的FBT
        if (n % 2 == 0) {
            return new ArrayList<TreeNode>();
        }

        // 初始化动态规划数组，用于存储TreeNode列表
        List<TreeNode>[] dp = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = new ArrayList<TreeNode>();
        }

        // 基础情况：有一个具有1个节点的可能的FBT
        dp[1].add(new TreeNode(0));

        // 从3开始迭代，直到n，每次增加2（因为节点数量必须是奇数）
        for (int i = 3; i <= n; i += 2) {
            // 从1迭代到i-1，每次增加2，找出可能的左子树大小
            for (int j = 1; j < i; j += 2) {
                // 遍历所有可能的左子树（dp[j]）
                for (TreeNode leftSubtree : dp[j]) {
                    // 遍历所有可能的右子树（dp[i - 1 - j]）
                    for (TreeNode rightSubtree : dp[i - 1 - j]) {
                        // 创建一个新节点作为根，值为0
                        TreeNode root = new TreeNode(0, leftSubtree, rightSubtree);
                        // 将新的树添加到具有i个节点的所有可能树列表中
                        dp[i].add(root);
                    }
                }
            }
        }
        // 返回具有n个节点的所有可能FBT的列表
        return dp[n];
    }




}
